πŸ‘©β€πŸ’» 64062. 징검닀리 κ±΄λ„ˆκΈ°

@Seongukbaek Posted May 12, 2022 Β· Updated May 12, 2022 Β· 3 min read

문제

Programmers - 징검닀리 κ±΄λ„ˆκΈ°

πŸ“ Logic

public int crossBridge(int[] stones, int k) { int friends = 0; int min = Integer.MAX_VALUE; int max = 0; // minκ³Ό max 사이에 건널 수 μžˆλŠ” μ΅œλŒ€ 인원 μˆ˜κ°€ 있음 for (int stone : stones) { if (stone < min) min = stone; if (stone > max) max = stone; } while (min <= max) { int mid = (min + max)/2; // 건널 수 μžˆλ‹€λ©΄, min을 1 μ¦κ°€μ‹œν‚€κ³  반볡 if (canCrossOver(stones, k, mid)) { min = mid + 1; friends = mid; } else { max = mid - 1; } } return friends; }
  • stones μ—μ„œ μ΅œμ†Ÿκ°’, μ΅œλŒ“κ°’μ„ μ°Ύμ•„ 이뢄탐색
  • canCrossOver() 둜 mid λͺ…이 건널 수 μžˆλŠ”μ§€ 확인

    • 건널 수 μžˆλ‹€λ©΄ min 을 update
    • 건널 수 μ—†λ‹€λ©΄ max λ₯Ό update

πŸ“„ CODE

μ½”λ“œ 보기/μ ‘κΈ°πŸ’«
import java.util.*; class StoneBridge { public StoneBridge() { } public int crossBridge(int[] stones, int k) { int friends = 0; int min = Integer.MAX_VALUE; int max = 0; // minκ³Ό max 사이에 건널 수 μžˆλŠ” μ΅œλŒ€ 인원 μˆ˜κ°€ 있음 for (int stone : stones) { if (stone < min) min = stone; if (stone > max) max = stone; } while (min <= max) { int mid = (min + max)/2; // 건널 수 μžˆλ‹€λ©΄, min을 1 μ¦κ°€μ‹œν‚€κ³  반볡 if (canCrossOver(stones, k, mid)) { min = mid + 1; friends = mid; } else { max = mid - 1; } } return friends; } private boolean canCrossOver(int[] stones, int k, int n) { int cantOver = 0; for (int stone : stones) { // 건널 수 μ—†λŠ” 돌 if (stone < n) { cantOver++; } else cantOver = 0; // 건널 수 μ—†λŠ” λŒλ‹€λ¦¬κ°€ k개 연속이라면 건널 수 μ—†μŒ! if (cantOver == k) return false; } return true; } } class Solution { public int solution(int[] stones, int k) { StoneBridge sb = new StoneBridge(); return sb.crossBridge(stones, k); } }

✏️ Review

  • 0이 K 개 연속이라면, 더 이상 건널 수 μ—†λ‹€λŠ” 큰 쑰건을 μ‰½κ²Œ μ•Œ 수 μžˆμ—ˆμœΌλ‚˜, νš¨μœ¨μ„± ν…ŒμŠ€νŠΈκ°€ μžˆλŠ” κ²ƒμœΌλ‘œ λ³΄μ•˜μ„ λ•Œ, μ–΄λ–€ μ•Œκ³ λ¦¬μ¦˜μ„ μ‚¬μš©ν•΄μ•Ό ν•˜λŠ”μ§€ 감이 μ˜€μ§€ μ•Šμ•˜λ‹€.
  • κ²Œμ‹œνŒμ—μ„œ 이뢄 탐색을 μ‚¬μš©ν•œλ‹€λŠ” 것을 λ³΄μ•˜κ³ , μ½”λ“œλ₯Ό λŒ€κ°• μ°Έκ³ ν•˜μ˜€λ‹€. 보고 λ‚˜λ‹ˆ μ™œ 이뢄 탐색을 μ‚¬μš©ν•΄μ•Ό ν•˜λŠ”μ§€λ₯Ό 이해할 수 μžˆμ—ˆλ‹€.
@Seongukbaek
배우고 μ •λ¦¬ν•˜κ³  κ³΅μœ ν•˜λŠ” λŒ€ν•™μƒ λ°±μ„±μš±μž…λ‹ˆλ‹€ πŸ˜€